#ifndef __LISTA_H__
#define __LISTA_H__

using namespace std;

template <class T> 
struct nodo_lista{
       nodo_lista<T> *prox;
       nodo_lista<T> *ant;
       T      elem;        
};

template <class T>
class ListaEnlazada {
    public:
        ListaEnlazada();
        ~ListaEnlazada();
        void agregarOrdenado(const T& elem );
        void agregarAtras(const T& elem);
        bool pertenece(const T& elem) const;
        nodo_lista<T>* buscar(const T& elem) const;
        void borrarElemento(nodo_lista<T>* elem);

        void vaciar();
        bool estaVacia() const;
        
        bool operator==(const ListaEnlazada<T> otra) const;

        ListaEnlazada<T>& operator=(const ListaEnlazada<T>& otra);

    template <class T2>
		friend ostream& operator<<(ostream&, const ListaEnlazada<T2>&);
        
            
    private:
        nodo_lista<T> *primero;
        nodo_lista<T> *ultimo;
        int    cant;        
};

template <class T>
ListaEnlazada<T>::ListaEnlazada()
{
    primero=0;
    ultimo=0;
    cant=0;
}

template <class T>
ListaEnlazada<T>::~ListaEnlazada()
{
    vaciar();
}

template <class T>
bool ListaEnlazada<T>::operator==(const ListaEnlazada<T> otra) const
{
    bool res = true;
    nodo_lista<T> *aux1;
    nodo_lista<T> *aux2;
    aux1=primero;
    aux2=otra.primero;

    if (cant != otra.cant)
    {
        res = false;
    }
    else 
    {

         while (aux1!=0 && aux2!=0 && res==true)
         {
         res = res && (aux1->elem == aux2->elem); 
         aux1=aux1->prox; 
         aux2=aux2->prox;
         }    
    }            
    return res;
}


template <class T>
nodo_lista<T>* ListaEnlazada<T>::buscar(const T& elem) const
{
    nodo_lista<T> *aux = primero;
    while((aux != 0) && (aux->elem != elem))
    {
        aux = aux->prox;    
    }
    return aux;
}

template <class T>
bool ListaEnlazada<T>::pertenece(const T& elem) const
{
    return (buscar(elem)!= 0);
}
     
template <class T>
void ListaEnlazada<T>::agregarOrdenado(const T& elem)
{
    nodo_lista<T> *aux;
    nodo_lista<T> *nuevo;
    nuevo = new nodo_lista<T>;
    nuevo->elem = elem;
     
     
    if(primero == 0)
    {
        nuevo->prox = 0;
        nuevo->ant = 0;
        primero = nuevo;
        ultimo = nuevo;
    }
    else 
    {
        aux = primero;    
        while( (aux->prox != 0) && (elem > aux->prox->elem)  )
        {
            aux = aux->prox;
        }
        
        if (( aux -> prox == 0) && (elem > aux->elem))
        {
            nuevo -> prox = 0;
            nuevo -> ant = aux;
            aux -> prox = nuevo;
            ultimo = nuevo;
        }
        else
        {
            if ((aux -> ant == 0) && (elem < aux->elem))
            {
                nuevo -> ant = 0;
                nuevo -> prox = aux;
                aux -> ant = nuevo;
                primero = nuevo;
            }
            else
            {
                nuevo -> ant = aux;
                nuevo -> prox = aux -> prox;
                aux -> prox -> ant = nuevo;
                aux -> prox = nuevo;
            }
           
             
        }       
    }
    cant++;
}


template<class T>
void ListaEnlazada<T>::borrarElemento(nodo_lista<T>* elem)
{                    
    nodo_lista<T> *anterior;
    nodo_lista<T> *proximo;
    
    anterior = elem->ant;
    proximo = elem->prox;
    
    delete elem;
    
    if (anterior==0)
    {
        primero=proximo;
    }
    else
    {    
        anterior->prox=proximo;
    }

    if (proximo==0)
    {
        ultimo=anterior;
    }
    else
    {    
        proximo->ant=anterior;
    }
 cant--; 
}

template<class T>
ListaEnlazada<T>& ListaEnlazada<T>::operator=(const ListaEnlazada<T>& otra)
{
    if (this != &otra) 
    {
        nodo_lista<T> *aux;
        aux = otra.primero;
    
        vaciar();
 
        while(aux != 0)
        {
            agregar(aux);
            aux = aux -> prox;
        }
    }
    return *this;
}


template<class T>
void ListaEnlazada<T>::agregarAtras(const T& elem)
{
    nodo_lista<T> *nuevo;
    nuevo = new nodo_lista<T>;

    if (estaVacia())
    {
        primero=nuevo;
        nuevo->prox=0;
        nuevo->ant=0;
    }
    else
    {    
        ultimo -> prox = nuevo;
        nuevo -> ant = ultimo;
    }
    nuevo -> prox = 0;        
    nuevo -> elem = elem;        
    ultimo = nuevo;
    cant++; 
}

template<class T>          
bool ListaEnlazada<T>::estaVacia() const
{
    return (ultimo==0 && primero==0);
}          

template<class T>
void ListaEnlazada<T>::vaciar()
{      
    nodo_lista<T> *aux;
    while (primero != 0)
    {
        aux = primero->prox;
        delete primero;
        primero = aux;
    }
    ultimo = 0;
    cant = 0; 
}


template <class T2>
ostream& operator<<(ostream& salida, const ListaEnlazada<T2>& lista)
{
    nodo_lista<T2> *aux;
    
    aux=lista.primero;
    
    while (aux!=0)
    {
        salida<< aux->elem << ",";
        aux=aux->prox;
    }
    return salida;
}


#endif

